package lc;

import org.junit.Test;

public class Ex400 {
    class Solution2 {
        public int findNthDigit(int n) {
            long start = 1, digit = 0, next;
            long ds = 9L;
            long order = 1L;
            // long ds = (long)(Math.pow(10, digit) * 9), next;
            while ((next = start + ds) <= n) {
                long tmp = (long)(Math.pow(10, digit) * 9);
                order += tmp;
                start = next;
                digit++;
                ds = (long)(Math.pow(10, digit) * 9) * (digit + 1);
            }
            System.out.println(start + "\t" + order);
            long step = (n - start) / (digit + 1);
            start += step * (digit + 1);
            order += step;

            System.out.println(start + "\t" + order);
    
            String t = order + "";
            long idx = n - start + 1;
            for (char c: t.toCharArray()) {
                idx--;
                if (idx == 0) {
                    return (int)(c - '0');
                }
            }
    
            return 0;
        }
    }

    class Solution {
        public int findNthDigit(int n) {
            int d = 0;
            long cur = 0, cnt = 9L;
            while (cur + cnt * (d + 1) < n) {
                d++;
                cur += cnt * d;
                cnt *= 10;
            }

            cur++;
            long start = (int)Math.pow(10, d);
            d++;
            int tmp = (int)(n - cur) / d;
            start += tmp;
            cur += tmp * d;
            int t = (int)cur + d - n, res = 0;
            while (t > 0) {
                res = (int)start % 10;
                start /= 10;
                t--;
            }
            return res;
        }
    
        public int findCount(int d) {
            return (int)Math.pow(10, d - 1) * 9;
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        System.out.println(s.findNthDigit(1000000000));
    }
}
